// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

const int N = 1e5+50;
typedef long long LL;

int n, m;

vector<int> G[N];

int dep[N];

vector<int> path;

int tar;
void quitf(int u, int v, int d) {
    int n = sz(path);
    puts("2");
    printf("%d\n", d);
    for (int i=1; i<=d; ++i)
        printf("%d%c", path[n-i], i==d? '\n':' ');
    exit(0);
}
void dfs(int u, int fa, int d) {
    // dbg(u, fa, d);
    dep[u] = d;
    path.push_back(u);

    for (int v : G[u]) {
        if (!dep[v] && v != fa) {
            dfs(v, u, d+1);
        } else if (dep[v] && dep[u]-dep[v]+1>=tar) {
            quitf(u, v, dep[u]-dep[v]+1);
        }
    }
    path.pop_back();
}

vector<int> dat[N];

int main(int argc, char const *argv[]) {
    // code'
    scanf("%d%d", &n, &m);
    tar = ceil(sqrt(n));
    for (int i=0; i<m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }



    dfs(1, 1, 1);
    int tar2 = tar-1;
    for (int i=1; i<=n; ++i) {
        dat[dep[i] % tar2].push_back(i);
    }

    for (int i=0; i<tar2; ++i) {
        if (dat[i].size() >= tar) {
            puts("1");
            for (int j=0; j<tar; ++j)
                printf("%d%c", dat[i][j], j==tar-1? '\n':' ');
            return 0;
        }
    }

    return 0;
}
